#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>


typedef char DataType;
typedef struct Stack
{
    DataType* data;
    int top;
    int capacity;
}Stack;


void Init(Stack* st);
void Push(Stack* st, DataType x);
void Pop(Stack* st);
DataType GetTop(Stack* st);
bool Empty(Stack* st);


void Init(Stack* st)
{
    assert(st);


    st->data = NULL;
    st->top = 0;
    st->capacity = 0;
}


void Push(Stack* st, DataType x)
{
    assert(st);


    if (st->capacity == st->top)
    {
        int newcapacity = (st->capacity == 0) ? 4 : st->capacity * 2;


        DataType* temp = (DataType*)realloc(st->data, sizeof(DataType) * newcapacity);
        if (temp == NULL)
        {
            perror("realloc fail");
            exit(-1);
        }


        st->data = temp;
        st->capacity = newcapacity;
    }


    st->data[st->top++] = x;
}


void Pop(Stack* st)
{
    assert(st);
    assert(st->top > 0);


    st->top--;
}


DataType GetTop(Stack* st)
{
    assert(st);
    assert(st->top > 0);


    return st->data[st->top - 1];
}


bool Empty(Stack* st)
{
    assert(st);


    return (st->top == 0);
}


bool isValid(char* s) {


    Stack st;
    Init(&st);
    while (*s)
    {
        if (*s == '[' || *s == '{' || *s == '(')
        {
            Push(&st, *s);
        }
        else
        {


            if (Empty(&st))
                return false;


            char ch = GetTop(&st);
            Pop(&st);
            if ((*s == ']' && ch != '[') ||
                (*s == '}' && ch != '{') ||
                (*s == ')' && ch != '('))
            {
                return false;
            }
        }
        s++;
    }


    if (!Empty(&st))
        return false;
    return true;
}